{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Circular Permutation in Binary Representation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: circularPermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #循环码排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数&nbsp;<code>n</code> 和 <code>start</code>。你的任务是返回任意 <code>(0,1,2,,...,2^n-1)</code> 的排列 <code>p</code>，并且满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>p[0] = start</code></li>\n",
    "\t<li><code>p[i]</code> 和 <code>p[i+1]</code>&nbsp;的二进制表示形式只有一位不同</li>\n",
    "\t<li><code>p[0]</code> 和 <code>p[2^n -1]</code>&nbsp;的二进制表示形式也只有一位不同</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, start = 3\n",
    "<strong>输出：</strong>[3,2,0,1]\n",
    "<strong>解释：</strong>这个排列的二进制表示是 (11,10,00,01)\n",
    "     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, start = 2\n",
    "<strong>输出：</strong>[2,6,7,5,4,0,1,3]\n",
    "<strong>解释：</strong>这个排列的二进制表示是 (010,110,111,101,100,000,001,011)\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 16</code></li>\n",
    "\t<li><code>0 &lt;= start&nbsp;&lt;&nbsp;2^n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [circular-permutation-in-binary-representation](https://leetcode.cn/problems/circular-permutation-in-binary-representation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [circular-permutation-in-binary-representation](https://leetcode.cn/problems/circular-permutation-in-binary-representation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3', '3\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        def gray(x):\n",
    "            return x^(x>>1)\n",
    "        \n",
    "        array = [gray(i) for i in range(2**n)]\n",
    "        idx =array.index(start)\n",
    "        return array[idx:] + array[:idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        g = [i ^ (i >> 1) for i in range(1 << n)]\n",
    "        j = g.index(start)\n",
    "        return g[j: ] + g[: j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        a = [i ^ (i >> 1) for i in range(1 << n)]\n",
    "        k = a.index(start)\n",
    "        return a[k:]+a[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        res = [0] * (1 << n)\n",
    "        for i in range(1<<n):\n",
    "            res[i] = (i>>1) ^ i ^ start\n",
    "        return res        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [start]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(len(ans) - 1, -1, -1):\n",
    "                ans.append(((ans[j] ^ start) | (1 << (i - 1))) ^ start)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        def graycode(n):\n",
    "            stack = [0]\n",
    "            num = 1\n",
    "            for i in range(n):\n",
    "                for j in range(len(stack)-1,-1,-1):\n",
    "                    stack.append(num + stack[j])\n",
    "                num <<= 1\n",
    "            return stack\n",
    "\n",
    "        num = graycode(n)\n",
    "        index = num.index(start)\n",
    "        return num[index:] + num[:index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        g = [i ^ (i >> 1) for i in range(1 << n)]\n",
    "        j = g.index(start)\n",
    "        return g[j:] + g[:j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        g = [i ^ (i >> 1) for i in range(1 << n)]\n",
    "        j = g.index(start)\n",
    "        return g[j:] + g[:j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        res, head = [0], 1\n",
    "        for i in range(n):\n",
    "            for j in range(len(res)-1, -1 ,-1):\n",
    "                res.append(head + res[j])\n",
    "            head <<= 1\n",
    "        idx = res.index(start)\n",
    "        return res[idx:] + res[:idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        #格雷编码的变式\n",
    "        ans=[0]*(1<<n)\n",
    "        for i in range(1<<n):\n",
    "            ans[i]=(i>>1)^i^start\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        g = [i ^ (i >> 1) for i in range(1 << n)]\n",
    "        j = g.index(start)\n",
    "        return g[j:] + g[:j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        a = [0,1]\n",
    "        for i in range(1,n):\n",
    "            t = len(a)\n",
    "            c = a[::-1]\n",
    "            for j in range(t):\n",
    "                c[j] += t\n",
    "            a = a + c\n",
    "        t = len(a)\n",
    "        k = a.index(start)\n",
    "        return a[k:]+a[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans, t = [0], 1\n",
    "        for i in range(n):\n",
    "            sz = len(ans)\n",
    "            for k in range(sz - 1, -1, -1):\n",
    "                ans.append(t + ans[k])\n",
    "            t <<= 1\n",
    "        for i, e in enumerate(ans):\n",
    "            if e == start:\n",
    "                return ans[i:] + ans[:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans, t = [0], 1\n",
    "        for i in range(n):\n",
    "            sz = len(ans)\n",
    "            for k in range(sz - 1, -1, -1):\n",
    "                ans.append(t + ans[k])\n",
    "            t <<= 1\n",
    "        for i, e in enumerate(ans):\n",
    "            if e == start:\n",
    "                s = i\n",
    "        return ans[s:] + ans[:s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        x = 1\n",
    "        offset = 0\n",
    "        while len(ans) != 1 << n:\n",
    "            m = len(ans)\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                ans.append(ans[i] | x)\n",
    "            x <<= 1\n",
    "        offset = ans.index(start)\n",
    "        return ans[offset:] + ans[:offset]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\r\n",
    "        g = [i ^ (i >> 1) for i in range(1 << n)]\r\n",
    "        i = g.index(start)\r\n",
    "        return g[i:] + g[:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        #格雷编码的变式\n",
    "        ans=[0]*(1<<n)\n",
    "        for i in range(1<<n):\n",
    "            ans[i]=(i>>1)^i^start\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        return [i ^ (i >> 1) ^ start for i in range(1 << n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        res = list()\n",
    "        for i in range(1 << n):\n",
    "            res.append(i ^ (i>>1))\n",
    "        while res[0] != start:\n",
    "            res.append(res.pop(0))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        a = [0,1]\n",
    "        for i in range(1,n):\n",
    "            t = len(a)\n",
    "            c = a[::-1]\n",
    "            for j in range(t):\n",
    "                c[j] += t\n",
    "            a = a + c\n",
    "        t = len(a)\n",
    "        k = a.index(start)\n",
    "        return a[k:t]+a[0:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [start]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(len(ans) - 1, -1, -1):\n",
    "                ans.append(((ans[j] ^ start) | (1 << (i - 1))) ^ start)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [start]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(len(ans) - 1, -1, -1):\n",
    "                ans.append(((ans[j] ^ start) | (1 << (i - 1))) ^ start)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n, start):\n",
    "        result = [1]* pow(2,n)\n",
    "        for i in range(len(result)):\n",
    "            result[i] = i ^ int(i/2)\n",
    "        startIndex = result.index(start)\n",
    "        return result[startIndex:]+result[:startIndex]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        N = 1 << n\n",
    "        greCode = []\n",
    "        for i in range(N):\n",
    "            greCode.append(i ^ (i >> 1))\n",
    "        start_index = greCode.index(start)\n",
    "        res = [start]\n",
    "        for i in range(1, N):\n",
    "            res.append(greCode[(start_index+i) % N])\n",
    "        return res\n",
    "\n",
    "        # 公式法\n",
    "        ans = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            ans[i] = (i >> 1) ^ i ^ start\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        res = [start]\n",
    "        for i in range(n):\n",
    "            for j in range(len(res)-1,-1,-1):\n",
    "                res.append(((res[j]^start)|(1<<i))^start)\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            for m in range(n):\n",
    "                ans[i] |= i ^ (i >> 1)\n",
    "        for i, v in enumerate(ans):\n",
    "            if v == start:\n",
    "                return ans[i:]+ans[:i]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        x = 1\n",
    "        offset = 0\n",
    "        while len(ans) != 1 << n:\n",
    "            m = len(ans)\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                ans.append(ans[i] | x)\n",
    "                if ans[-1] == start:\n",
    "                    offset = len(ans) - 1\n",
    "            x <<= 1\n",
    "        return ans[offset:] + ans[:offset]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        N = 1 << n\n",
    "        greCode = []\n",
    "        for i in range(N):\n",
    "            greCode.append(i ^ (i >> 1))\n",
    "        start_index = greCode.index(start)\n",
    "        res = [start]\n",
    "        for i in range(1, N):\n",
    "            res.append(greCode[(start_index+i) % N])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        x = 1\n",
    "        while len(ans) != 1 << n:\n",
    "            for i in range(len(ans) - 1, -1, -1):\n",
    "                ans.append(ans[i] | x)\n",
    "            x <<= 1\n",
    "        ans = [ans[i] ^ start for i in range(len(ans))]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        x = 1\n",
    "        while len(ans) != 1 << n:\n",
    "            for i in range(len(ans) - 1, -1, -1):\n",
    "                ans.append(ans[i] | x)\n",
    "            x <<= 1\n",
    "        ans = [ans[i] ^ start for i in range(len(ans))]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        x = 1\n",
    "        while len(ans) != 1 << n:\n",
    "            for i in range(len(ans) - 1, -1, -1):\n",
    "                ans.append(ans[i] | x)\n",
    "            x <<= 1\n",
    "        ans = [ans[i] ^ start for i in range(len(ans))]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        def reverse(nums: list,add_num: int):\n",
    "            return [nums[len(nums)-1-i]+add_num for i in range(len(nums))]\n",
    "        res = [0]\n",
    "        for i in range(n):\n",
    "            res += reverse(res,pow(2,i))\n",
    "        return res[res.index(start):]+res[:res.index(start)]\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        x = [0, 1]\n",
    "        for k in range(1, n):\n",
    "            x.extend([i + (1<<k) for i in reversed(x)])\n",
    "        j = x.index(start)\n",
    "        return x[j:] + x[:j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        x = 1\n",
    "        offset = 0\n",
    "        while len(ans) != 1 << n:\n",
    "            m = len(ans)\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                ans.append(ans[i] | x)\n",
    "                if ans[-1] == start:\n",
    "                    offset = len(ans) - 1\n",
    "            x <<= 1\n",
    "        n = len(ans)\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            index = i + offset\n",
    "            index = index if index < n else index % n\n",
    "            ret.append(ans[index])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        def grayCode(n):\n",
    "            pre = [0, 1]\n",
    "            for i in range(2, n + 1):\n",
    "                next = pre.copy()\n",
    "                for x in reversed(pre):\n",
    "                    next.append(x + 2 ** (i - 1))\n",
    "                pre = next\n",
    "            return pre\n",
    "        ans = grayCode(n)\n",
    "        # print(ans)\n",
    "        for i in range(len(ans)):\n",
    "            if ans[i] == start:\n",
    "                return ans[i:] + ans[:i]\n",
    "        return ans                                                                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            for m in range(n):\n",
    "                ans[i] |= ((i & (1 << m + 1)) >> 1) ^ (i & (1 << m))\n",
    "        for i, v in enumerate(ans):\n",
    "            if v == start:\n",
    "                return ans[i:]+ans[:i]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        num_list=[0]\n",
    "        for k in range(n):\n",
    "            temp=[num+2**k for num in num_list]\n",
    "            num_list+=temp[::-1]\n",
    "        idx=num_list.index(start)\n",
    "        return num_list[idx:]+num_list[:idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [-1] * (1 << n)\n",
    "        ans[0] = start\n",
    "        ans[-1] = start ^ 1\n",
    "        visited = {ans[0], ans[-1]}\n",
    "        for i in range(1, 1 << (n-1)):\n",
    "            j = 0\n",
    "            while j < 16:\n",
    "                if ans[i-1] ^ (1 << j) not in visited:\n",
    "                    ans[i] = ans[i-1] ^ (1 << j)\n",
    "                    visited.add(ans[i])\n",
    "                    break\n",
    "                j += 1\n",
    "            j = 0\n",
    "            while j < 16:\n",
    "                if ans[-i] ^ (1 << j) not in visited:\n",
    "                    ans[-i-1] = ans[-i] ^ (1 << j)\n",
    "                    visited.add(ans[-i-1])\n",
    "                    break\n",
    "                j += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        ans = [-1] * (1 << n)\n",
    "        ans[0] = start\n",
    "        ans[-1] = start ^ 1\n",
    "        visited = {ans[0], ans[-1]}\n",
    "        for i in range(1, 1 << (n-1)):\n",
    "            j = 0\n",
    "            while j < 16:\n",
    "                if ans[i-1] ^ (1 << j) not in visited:\n",
    "                    ans[i] = ans[i-1] ^ (1 << j)\n",
    "                    visited.add(ans[i])\n",
    "                    break\n",
    "                j += 1\n",
    "            j = 0\n",
    "            while j < 16:\n",
    "                if ans[-i] ^ (1 << j) not in visited:\n",
    "                    ans[-i-1] = ans[-i] ^ (1 << j)\n",
    "                    visited.add(ans[-i-1])\n",
    "                    break\n",
    "                j += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from typing import *\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        def cyclic_code(n):\n",
    "            if n <= 0: return []\n",
    "            codes = ['0', '1']\n",
    "            for i in range(n - 1): codes = [code + '0' for code in codes] + [code + '1' for code in reversed(codes)]\n",
    "            return codes\n",
    "        cyc_lst = cyclic_code(n)\n",
    "        lst = [int(x, 2) for x in cyc_lst]\n",
    "        idx = lst.index(start)\n",
    "        return lst[idx:] + lst[:idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        def dfs(x):\n",
    "            vis[x] = 1\n",
    "            ans.append(x)\n",
    "            for i in range(n):\n",
    "                if not vis[x ^ (1 << i)]:\n",
    "                    dfs(x ^ (1 << i))\n",
    "            \n",
    "        \n",
    "        ans = []\n",
    "        vis = [0] * (1 << n)\n",
    "        dfs(start)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularPermutation(self, n: int, start: int) -> List[int]:\n",
    "        def dfs(x):\n",
    "            vis[x] = 1\n",
    "            for i in range(n):\n",
    "                if not vis[x ^ (1 << i)]:\n",
    "                    dfs(x ^ (1 << i))\n",
    "            ans.append(x)\n",
    "        \n",
    "        ans = []\n",
    "        vis = [0] * (1 << n)\n",
    "        dfs(start)\n",
    "        return ans[::-1]\n",
    "\n",
    "'''\n",
    "11\n",
    "10\n",
    "00\n",
    "01\n",
    "'''"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
